Blindfolded Men Getting Together
I’ve heard many fun problems in which blindfolded parachutists are dropped somewhere and they need to meet up once they’re on the ground. They can’t shout or purposefully leave traces behind. They will recognize each other as soon as they bump into each other. Their goal is to get to the same assembly point. They can design their strategy in advance.
Here is the first problem in a series that gets increasingly difficult:
Two parachutists are dropped at different locations on a straight line at the same time. Both have an excellent sense of direction and a good geographical memory, so both know where they are at any moment with respect to their starting point on the line. What’s their strategy?
The strategy is that the first person stands still and the second one goes forward and back repeatedly, increasing the distance of each leg until they collide.
In the next variation, both are required to execute the same program, that is, if one stands still, then both stand still. To compensate for this increased difficulty, they are allowed to leave their parachutes anywhere. And both of them will recognize the other’s parachute if they bump into it.
In the third variation, the set-up is similar to the previous problem, but they are not allowed to change the direction of their movement. To their advantage, they know which way East is.
I recently heard a 2-D version from my son Sergei in which the parachutists are ghosts. That means that when they bump into each other they go through each other without even recognizing the fact that they met:
Several blindfolded men are sleeping at different locations on a plane. Each wakes up, not necessarily at the same time. At the moment of waking up, each of them receives the locations of all the others in relation to himself at that moment. They are not allowed to interact, nor will they receive any further information as time passes. They need to get together in one place. How can they do that, if they are allowed to decide on their strategy in advance?
They do not know where North is. So they can’t go to the person at the most Northern point. Also they do not know how locations correspond to people, so they can’t all go to where, say, Peter is. Let us consider the case of two men. Suppose they decide to go to the middle of the segment of two locations they receive when they awake. But they get different locations because they wake up at different times. Suppose the first person wakes up and goes to the middle. The fact that he walks while the other is sleeping, means that he changes the middle. So when the second person wakes up, his calculated middle is different from the one calculated by the first person. Consequently, they will never manage to meet. Hence, the solution should be different.
Actually Sergei gave me a more difficult problem:
Not only do they need to meet, but they need to stay together for a predefined finite time period.
Here is as bonus problem.
Share:If there are three parachutists, it is possible to end up in a meeting place and stay there indefinitely. For four people it is often possible too.
passerby:
In the second variation of the problem, if they both execute the same program, since the distance between the two remains constant, how can they ever meet at a single point?
21 December 2010, 3:14 pmTanya Khovanova:
passerby,
Hint: The same program doesn’t mean identical movements.
21 December 2010, 3:19 pmasv:
Assuming parachutists are happy with a “stupid” rather than “least walking distance” strategy and ‘both know where they are at any moment with respect to their starting point on the line’ means they know a distance up to the starting point, why they shouldn’t go to the starting point using their memory ?
23 December 2010, 12:42 pmBasil:
Thanks for the posting! I’m going to use your problem for my “Got Skill” in class this January.
23 December 2010, 1:22 pmTanya Khovanova:
asv,
Each has its own starting point.
23 December 2010, 2:57 pmJur:
Second variation of the problem: “both are required to execute the same program, that is, if one stands still, then both stand still” and “Hint: The same program doesn’t mean identical movements.”
26 December 2010, 5:02 pmBut when program required (for example)- stay still with other’s parachute for 20 time unit – they will stay still not simultaneously?
Student:
For the plane one, isn’t it simple? the method they would use would be head to the spot with the most people at it, except the first person, who would recognize that there are no places with two people, and simply choose an area where they would meet by going to another person
3 January 2011, 10:10 amTanya Khovanova:
Student,
How does the first person knows that he/she is the first?
3 January 2011, 4:15 pmStudent:
Well, there are two cases for when he wakes up
4 January 2011, 9:58 ameither there IS a place where there is more than one person, or there isn’t
in the first case, he wouldn’t recognize he was first, and would simply head to the largest group
in the second case, he would realize that the only way he wouldn’t see a largest group would be if he was first, so he would simple pick another person to got to (or if say, there are two spots with two people, he would head to one of those groups) so he picks which one would become the largest, and everyone else would have to see that one as he largest
Tanya Khovanova:
Student,
Suppose two people wake up at the same time.
4 January 2011, 10:40 amBill:
Also, the second person may wake up while the first is en route. The ghosts are not given vectors, only locations.
I’ll stick with the 1-D problems for now.
Variation 2: Each parachutist should execute the following program: 1) drop the parachute at the starting point, 2) go forward and backward repeatedly increasing the distance each time using a pre-determined pattern, 3) stop when you hit the other person’s parachute (or the other person).
Variation 3: Each parachutist should execute the following program: 1) drop the parachute at the starting point, 2) go East at a pre-determined slow speed, 3) speed up when you hit the other person’s parachute.
I have to think about the 2-D problem some more.
4 January 2011, 6:15 pmStudent:
Well for the en route, i’m sure they know time, and can realize when a person is changing their position if they see the position moving, they just wouldn’t know who it is
as for the two people waking up at the sametime, since they are allowed to pick a strategy before hand, they can pick say, a wlking motion that is set in an ordered way, such as zigzaging or something along those lines, in which the heiarchy would be decided before hand, and then if two people wake up, the one loweron the hierachy would follow the one on the higher end of the hierachy.
5 January 2011, 9:57 ammashplum:
If the parachutists in the plane are given Cartesian coordinates, why can’t they all meet at the one with the greatest x-value? If there are two or more with the greatest x-value, use the y-value as a tie breaker. If they take the shortest route, their own coordinates will never be greater than their destination so they won’t foul up any others who wake up later. The one who has the greatest x-value will know it, since all the other x-values will be negative.
The only way this wouldn’t work is if the orientation of the axes are different for each person. But this should be specified in the problem if it is the case.
12 April 2011, 6:39 pm